package binarysearch;

public class 能覆盖所有数组节点的信号塔最小半径 {
}
// https://binarysearch.com/problems/Minimum-Light-Radius 能覆盖所有数组节点的信号塔最小半径
class Solution {
            public double solve(int[] nums) {
                // 直径最小为0  最大为 nums[nums.length - 1]
                // 求最小的直径  要使得 最后 l = r  需要保证满足条件时 mid 不变  不满足时mid  + 1  因此可以分为 l - mid , mid + 1 - r
                int l = 0, r =  nums[nums.length - 1];
                while(l < r) {
                    int mid = (l + r) >> 1; 
                    if(canCoverAll(nums, mid)) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                return (l + 0.0) / 2; // 保证最后返回的是浮点数
            }

            // diam 直径   radius 半径
            private boolean canCoverAll(int[] nums, int diam) {
                // 不能使用3个直径加起来超过整个数组长度   因为信号塔只要能覆盖各自范围内的点即可， 可能三个范围不连续
                int end = diam + nums[0];
                int scopeCnt = 1;
                for(int i = 0; i < nums.length; i++) {
                    if(nums[i] > end) {
                        scopeCnt ++;
                        end = diam + nums[i];
                    }
                }
                return scopeCnt <= 3; // 是否能够分成三段
            }
        }
